<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            Rabin-Karp算法 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">Rabin-Karp算法</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-07-01 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>3.6k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>17 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>见到好几次了，感觉不是很难，学一手，本来想详细的写一下完整的Rabin-Karp解析的，但是目前确实时间有点紧，加上自己也没做几题，理解的可能还不到位，等后面有时间再来补吧</p>
</blockquote>
<h2 id="1044-最长重复子串"><a href="#1044-最长重复子串" class="headerlink" title="1044. 最长重复子串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-duplicate-substring/" >1044. 最长重复子串<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>困难</strong></p>
<p>给出一个字符串 <code>S</code>，考虑其所有<strong>重复子串</strong>（<code>S</code> 的连续子串，出现两次或多次，可能会有重叠）。</p>
<p>返回<strong>任何</strong>具有最长可能长度的重复子串。（如果 <code>S</code> 不含重复子串，那么答案为 <code>&quot;&quot;</code>。）</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：&quot;banana&quot;</span><br><span class="line">输出：&quot;ana&quot;</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：&quot;abcd&quot;</span><br><span class="line">输出：&quot;&quot;</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li> <code>2 &lt;= S.length &lt;= 10^5</code></li>
<li> <code>S</code> 由小写英文字母组成。</li>
</ol>
<p><strong>解法一</strong></p>
<p>看题解区学习了一下，整体的思路倒是不难，主要就是一个<code>rolling hash</code>的过程，然后就是关于MOD的选取，到现在也不是很清楚怎么选MOD。。。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">longestDupSubstring</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = S.length();</span><br><span class="line">    <span class="keyword">int</span> [] nums =<span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; S.length(); i++) &#123;</span><br><span class="line">        nums[i] =  S.charAt(i) - <span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">long</span> MOD =  <span class="number">1L</span>&lt;&lt;<span class="number">32</span>;</span><br><span class="line">    <span class="keyword">int</span> B = <span class="number">26</span>; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> right = n - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> start = -<span class="number">1</span>, mlen = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span> temp = RabinKarp(mid, B, nums, MOD);</span><br><span class="line">        <span class="keyword">if</span> (temp != -<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (mid &gt; mlen)&#123;</span><br><span class="line">                mlen = mid;</span><br><span class="line">                start = temp;</span><br><span class="line">            &#125;</span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> start == -<span class="number">1</span> ? <span class="string">&quot;&quot;</span> : S.substring(start, start + mlen);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">RabinKarp</span><span class="params">(<span class="keyword">int</span> len, <span class="keyword">int</span> B, <span class="keyword">int</span>[] nums, <span class="keyword">long</span> MOD)</span></span>&#123;</span><br><span class="line">    <span class="comment">//hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1</span></span><br><span class="line">    <span class="comment">//B^(len-1) (移除左端点时需要的值)</span></span><br><span class="line">    <span class="keyword">long</span> BL = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len - <span class="number">1</span>; i++)&#123;</span><br><span class="line">        BL = (BL * B) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//[0,len-1]的hash值</span></span><br><span class="line">    <span class="keyword">long</span> h = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)&#123;</span><br><span class="line">        h = (h * B + nums[i]) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Long&gt; set = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    set.add(h);</span><br><span class="line">    <span class="comment">//rolling hash</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= nums.length - len; i++)&#123;</span><br><span class="line">        <span class="comment">//+MOD是为了负数取模</span></span><br><span class="line">        h = (h - nums[i - <span class="number">1</span>] * BL % MOD + MOD) % MOD;</span><br><span class="line">        h = (h * B + nums[i + len - <span class="number">1</span>]) % MOD;</span><br><span class="line">        <span class="keyword">if</span> (set.contains(h))&#123;</span><br><span class="line">            <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        set.add(h);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>补充一下冲突检测，猜mod也太玄学了😂</p>
<blockquote>
<p>这个冲突检测的方法有问题，留下做个印证，正确的检测请直接看 解法三</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//写一波检测冲突的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">longestDupSubstring</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = S.length();</span><br><span class="line">    <span class="keyword">long</span> MOD = (<span class="keyword">long</span>) <span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line">    <span class="keyword">int</span> B = <span class="number">26</span>; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> right = n - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> start = -<span class="number">1</span>, mlen = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span> temp = RabinKarp(mid, B, S, MOD);</span><br><span class="line">        <span class="keyword">if</span> (temp != -<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (mid &gt; mlen)&#123;</span><br><span class="line">                mlen = mid;</span><br><span class="line">                start = temp;</span><br><span class="line">            &#125;</span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> start == -<span class="number">1</span> ? <span class="string">&quot;&quot;</span> : S.substring(start, start + mlen);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">RabinKarp</span><span class="params">(<span class="keyword">int</span> len, <span class="keyword">int</span> B, String S, <span class="keyword">long</span> MOD)</span></span>&#123;</span><br><span class="line">    <span class="comment">//hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1</span></span><br><span class="line">    <span class="comment">//B^(len-1) (移除左端点时需要的值)</span></span><br><span class="line">    <span class="keyword">long</span> BL = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len - <span class="number">1</span>; i++)&#123;</span><br><span class="line">        BL = (BL * B) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//[0,len-1]的hash值</span></span><br><span class="line">    <span class="keyword">long</span> h = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)&#123;</span><br><span class="line">        h = (h * B + S.charAt(i) - <span class="string">&#x27;a&#x27;</span>) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//这里肯定不能直接存字符串做冲突检测，太大了会MLE</span></span><br><span class="line">    <span class="comment">//存一个起始地址就可以了len已知</span></span><br><span class="line">    HashMap&lt;Long,Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    map.put(h, <span class="number">0</span>);</span><br><span class="line">    <span class="comment">//rolling hash</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= S.length() - len; i++)&#123;</span><br><span class="line">        <span class="comment">//+MOD是为了负数取模</span></span><br><span class="line">        h = (h - (S.charAt(i-<span class="number">1</span>) - <span class="string">&#x27;a&#x27;</span>) * BL % MOD + MOD) % MOD;</span><br><span class="line">        h = (h * B + (S.charAt(len + i -<span class="number">1</span>) - <span class="string">&#x27;a&#x27;</span>)) % MOD;</span><br><span class="line">        Integer start = map.get(h);</span><br><span class="line">        <span class="keyword">if</span> (start != <span class="keyword">null</span> &amp;&amp; S.substring(start, start + len).equals(S.substring(i, i + len)))&#123;</span><br><span class="line">            <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(h, i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>关于这个冲突检测有一个小问题，我尝试减小了<code>MOD</code>的大小，比如101，这样计算出来的结果在数据量较大的就不对了，得到的字符虽然确实是重复了，但是并不是最长的，按道理写了冲突检测后即使我MOD取1应该都是可以找出来的啊？======&gt;<br>在写上面这段话的时候突然想明白了，因为<code>MOD</code>取的太小，导致冲突的概率大大增加，而这里我做冲突检测的时候只保存了一个值，也就是说会有很多值被舍弃掉，也许你舍弃的值可能恰好就是最后的答案，字符越长，发生这种情况的概率就越高，所以说我这里冲突检测做的并不完全，能过也纯属运气，正确的冲突检测应该保存一个<code>List</code>链表，然后在发生冲突的时候在List中找有没有和当前字符相等的，这样一来，时间复杂度就会上去（其实这个过程就是设计Hash表的过程，链地址法解决冲突）</p>
</blockquote>
<p><strong>解法三</strong></p>
<p>下面的应该就没什么问题了，链地址法，时间复杂度会增大，耗时增加到了500ms+，但是确保了100%的正确率，这是值得的，这次把mod调小也不会出错了（但是可能会TLE，冲突变大了），总体来说，这几番折腾收获还是挺大的，好事还是要多磨啊</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//再写一波检测冲突。。。</span></span><br><span class="line"><span class="comment">//上面的写的有问题，检测不完全</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">longestDupSubstring</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = S.length();</span><br><span class="line">    <span class="keyword">long</span> MOD = (<span class="keyword">long</span>) <span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line">    <span class="keyword">int</span> B = <span class="number">26</span>; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> right = n - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> start = -<span class="number">1</span>, mlen = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span> temp = RabinKarp(mid, B, S, MOD);</span><br><span class="line">        <span class="keyword">if</span> (temp != -<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (mid &gt; mlen)&#123;</span><br><span class="line">                mlen = mid;</span><br><span class="line">                start = temp;</span><br><span class="line">            &#125;</span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> start == -<span class="number">1</span> ? <span class="string">&quot;&quot;</span> : S.substring(start, start + mlen);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">RabinKarp</span><span class="params">(<span class="keyword">int</span> len, <span class="keyword">int</span> B, String S, <span class="keyword">long</span> MOD)</span></span>&#123;</span><br><span class="line">    <span class="comment">//hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1</span></span><br><span class="line">    <span class="comment">//B^(len-1) (移除左端点时需要的值)</span></span><br><span class="line">    <span class="keyword">long</span> BL = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len - <span class="number">1</span>; i++)&#123;</span><br><span class="line">        BL = (BL * B) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//[0,len-1]的hash值</span></span><br><span class="line">    <span class="keyword">long</span> h = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; len; i++)&#123;</span><br><span class="line">        h = (h * B + S.charAt(i) - <span class="string">&#x27;a&#x27;</span>) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//这里肯定不能直接存字符串做冲突检测，太大了会MLE</span></span><br><span class="line">    <span class="comment">//存一个起始地址就可以了len已知</span></span><br><span class="line">    HashMap&lt;Long,List&lt;Integer&gt;&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    map.put(h, <span class="keyword">new</span> ArrayList()&#123;&#123;add(<span class="number">0</span>);&#125;&#125;);</span><br><span class="line">    <span class="comment">//rolling hash</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= S.length() - len; i++)&#123;</span><br><span class="line">        <span class="comment">//+MOD是为了负数取模</span></span><br><span class="line">        h = (h - (S.charAt(i-<span class="number">1</span>) - <span class="string">&#x27;a&#x27;</span>) * BL % MOD + MOD) % MOD;</span><br><span class="line">        h = (h * B + (S.charAt(len + i -<span class="number">1</span>) - <span class="string">&#x27;a&#x27;</span>)) % MOD;</span><br><span class="line">        List&lt;Integer&gt; starts = map.get(h);</span><br><span class="line">        <span class="keyword">if</span> (check(starts, i, S, len))&#123;</span><br><span class="line">            <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (starts == <span class="keyword">null</span>)&#123;</span><br><span class="line">            List&lt;Integer&gt; lis = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">            lis.add(i);</span><br><span class="line">            map.put(h, lis);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            starts.add(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">check</span><span class="params">(List&lt;Integer&gt; starts, <span class="keyword">int</span> i, String s, <span class="keyword">int</span> len)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(starts == <span class="keyword">null</span> || starts.size() &lt;= <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> left : starts) &#123;</span><br><span class="line">        <span class="keyword">if</span>(s.substring(left, left + len).equals(s.substring(i, i + len)))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h2 id="718-最长重复子数组"><a href="#718-最长重复子数组" class="headerlink" title="718. 最长重复子数组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/" >718. 最长重复子数组<i class="fas fa-external-link-alt"></i></a></h2><p>给两个整数数组 <code>A</code> 和 <code>B</code> ，返回两个数组中公共的、长度最长的子数组的长度。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">A: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">B: [<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">4</span>,<span class="number">7</span>]</span><br><span class="line">输出: <span class="number">3</span></span><br><span class="line">解释: </span><br><span class="line">长度最长的公共子数组是 [<span class="number">3</span>, <span class="number">2</span>, <span class="number">1</span>]。</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ol>
<li>1 &lt;= len(A), len(B) &lt;= 1000</li>
<li>0 &lt;= A[i], B[i] &lt; 100</li>
</ol>
<p><strong>解法一</strong></p>
<p>dp的解法是O(N^2)的，略显暴力，动态规划的解法放在<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/#718-%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84">dp专题</a>中，这里要介绍的是二分+字符串Hash的<code>O(NlogN)</code>的解法</p>
<p>这里直接莽过了，且效率极高（16ms），就不写冲突检测了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findLength</span><span class="params">(<span class="keyword">int</span>[] A, <span class="keyword">int</span>[] B)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> lenA = A.length, lenB = B.length;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> right = Math.min(lenA, lenB);</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left +(right - left) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span>(RabinKarp(A, B, mid))&#123;</span><br><span class="line">            res = Math.max(res, mid);</span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">RabinKarp</span><span class="params">(<span class="keyword">int</span>[] A,<span class="keyword">int</span>[] B, <span class="keyword">int</span> L)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> MOD = (<span class="keyword">int</span>) <span class="number">1e9</span>+<span class="number">7</span>, BASE = <span class="number">101</span>;</span><br><span class="line">    <span class="keyword">long</span> BL = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; L-<span class="number">1</span>; i++)&#123;</span><br><span class="line">        BL = (BL * BASE) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//hash(A[0,L-1]),hash(B[0,L-1])</span></span><br><span class="line">    <span class="keyword">long</span> hA = <span class="number">0</span>, hB = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; L; i++)&#123;</span><br><span class="line">        hA = (hA * BASE + A[i]) % MOD;</span><br><span class="line">        hB = (hB * BASE + B[i]) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Long&gt; set =<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    set.add(hA);</span><br><span class="line">    <span class="comment">//rolling hash A</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= A.length - L; i++)&#123;</span><br><span class="line">        hA = (hA - A[i-<span class="number">1</span>] * BL % MOD + MOD) % MOD;</span><br><span class="line">        hA = (hA * BASE + A[L + i -<span class="number">1</span>]) % MOD;</span><br><span class="line">        set.add(hA);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(set.contains(hB)) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    <span class="comment">//rolling hash B</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= B.length - L; i++)&#123;</span><br><span class="line">        hB = (hB - B[i-<span class="number">1</span>] * BL % MOD + MOD) % MOD;</span><br><span class="line">        hB = (hB * BASE + B[L + i -<span class="number">1</span>]) % MOD;</span><br><span class="line">        <span class="comment">//这里还可以做一下冲突检测，set中需要多存一些信息</span></span><br><span class="line">        <span class="keyword">if</span>(set.contains(hB))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="面试题-17-13-恢复空格"><a href="#面试题-17-13-恢复空格" class="headerlink" title="面试题 17.13. 恢复空格"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/re-space-lcci/" >面试题 17.13. 恢复空格<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子<code>&quot;I reset the computer. It still didn’t boot!&quot;</code>已经变成了<code>&quot;iresetthecomputeritstilldidntboot&quot;</code>。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典<code>dictionary</code>，不过，有些词没在词典里。假设文章用<code>sentence</code>表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。</p>
<p><strong>注意:</strong> 本题相对原题稍作改动，只需返回未识别的字符数</p>
<p><strong>示例：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：</span><br><span class="line">dictionary = [<span class="string">&quot;looked&quot;</span>,<span class="string">&quot;just&quot;</span>,<span class="string">&quot;like&quot;</span>,<span class="string">&quot;her&quot;</span>,<span class="string">&quot;brother&quot;</span>]</span><br><span class="line">sentence = <span class="string">&quot;jesslookedjustliketimherbrother&quot;</span></span><br><span class="line">输出： <span class="number">7</span></span><br><span class="line">解释： 断句后为<span class="string">&quot;jess looked just like tim her brother&quot;</span>，共<span class="number">7</span>个未识别字符。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  <code>0 &lt;= len(sentence) &lt;= 1000</code></li>
<li>  <code>dictionary</code>中总字符数不超过 150000。</li>
<li>  你可以认为<code>dictionary</code>和<code>sentence</code>中只包含小写字母。</li>
</ul>
<p><strong>解法一</strong></p>
<p>动态规划和Trie的解法左转<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/">动态规划</a>专题，这里记录下字符串Hash的做法，其实字符串Hash的做法相比字典树的做法会慢一点点，不过思路还是很值得学习的</p>
<p>这里看官方题解又学到了一点东西，这里在计算hash的时候加了一个1，这样我猜测就是为了避免0的出现，使得后面的base失效，使得冲突的概率变大，比如<code>aba</code>和<code>ba</code>可能就会被判成一样的字符，我下面的做法没有做减<code>a</code>的操作，而是取了更大的BASE，这里就不写冲突检测了，可以直接莽过，上面的第一题确实太离谱了，不按照官方题解的数据来就过不了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">respace</span><span class="params">(String[] dictionary, String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> BASE = <span class="number">131</span>;</span><br><span class="line">    <span class="keyword">long</span> MOD = Integer.MAX_VALUE;</span><br><span class="line">    HashSet&lt;Long&gt; set = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (String word : dictionary ) &#123;</span><br><span class="line">        set.add(hash(word, BASE, MOD));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n = s.length();</span><br><span class="line">    <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;=n ; i++) &#123;</span><br><span class="line">        dp[i] = dp[i-<span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">long</span> rollhash = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &gt;= <span class="number">1</span>; j--) &#123;</span><br><span class="line">            rollhash = (rollhash * BASE + s.charAt(j-<span class="number">1</span>)) % MOD;</span><br><span class="line">            <span class="keyword">if</span>(set.contains(rollhash))&#123;</span><br><span class="line">                <span class="comment">//注意这里是dp[j-1]，对应s.charAt(j-1)的前一个字符</span></span><br><span class="line">                dp[i] = Math.min(dp[i], dp[j-<span class="number">1</span>]);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(dp[i] == <span class="number">0</span>)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[n];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//注意需要逆向hash，上面计算的时候是j--，是逆向的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">long</span> <span class="title">hash</span><span class="params">(String s, <span class="keyword">int</span> BASE, <span class="keyword">long</span> MOD)</span></span>&#123;</span><br><span class="line">    <span class="keyword">long</span> h = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = s.length()-<span class="number">1</span>; i &gt;=<span class="number">0</span> ; i--) &#123;</span><br><span class="line">        h = (h * BASE + s.charAt(i)) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> h;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>这个解法也用到了Hash表，但是相比用Hash表存字符，存数字的时间复杂度会低很多，其实字符串Hash也就是为了避免在Hash表中存大量的字符，一来空间占用会非常大，二来对于字符串来说计算字符的<code>hashCode()</code>的时间复杂度也是O(N)不可忽略的，而数字长度固定，<code>hashCode()</code>直接返回值就行了</p>
</blockquote>
<h2 id="1316-不同的循环子字符串"><a href="#1316-不同的循环子字符串" class="headerlink" title="1316. 不同的循环子字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/distinct-echo-substrings/" >1316. 不同的循环子字符串<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>困难</strong></p>
<p>给你一个字符串 <code>text</code> ，请你返回满足下述条件的 <strong>不同</strong> 非空子字符串的数目：</p>
<ul>
<li>  可以写成某个字符串与其自身相连接的形式（即，可以写为 <code>a + a</code>，其中 <code>a</code> 是某个字符串）。</li>
</ul>
<p>例如，<code>abcabc</code> 就是 <code>abc</code> 和它自身连接形成的。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：text = <span class="string">&quot;abcabcabc&quot;</span></span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：<span class="number">3</span> 个子字符串分别为 <span class="string">&quot;abcabc&quot;</span>，<span class="string">&quot;bcabca&quot;</span> 和 <span class="string">&quot;cabcab&quot;</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：text = <span class="string">&quot;leetcodeleetcode&quot;</span></span><br><span class="line">输出：<span class="number">2</span></span><br><span class="line">解释：<span class="number">2</span> 个子字符串为 <span class="string">&quot;ee&quot;</span> 和 <span class="string">&quot;leetcodeleetcode&quot;</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  <code>1 &lt;= text.length &lt;= 2000</code></li>
<li>  <code>text</code> 只包含小写英文字母。</li>
</ul>
<p><strong>解法一</strong></p>
<p>哭了，看着KMP的tag进来的，结果发现KMP的不太会写，学习了题解的前缀和Hash的思路，还是有点收获</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span> BASE = <span class="number">131</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">long</span> MOD = (<span class="keyword">long</span>)<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">distinctEchoSubstrings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = s.length();</span><br><span class="line">    <span class="comment">//前缀hash和(前i个元素的hash值)</span></span><br><span class="line">    <span class="keyword">long</span>[] hashSum = <span class="keyword">new</span> <span class="keyword">long</span>[n+<span class="number">1</span>];</span><br><span class="line">    <span class="comment">//BASE的所有幂乘</span></span><br><span class="line">    <span class="keyword">long</span>[] pow = <span class="keyword">new</span> <span class="keyword">long</span>[n+<span class="number">1</span>];</span><br><span class="line">    pow[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    hashSum[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        hashSum[i] = (hashSum[i-<span class="number">1</span>]*BASE + s.charAt(i-<span class="number">1</span>)) % MOD;</span><br><span class="line">        pow[i] = (pow[i-<span class="number">1</span>]*BASE) % MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Long&gt; set = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="comment">//枚举所有偶数长度的子串</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> len = <span class="number">2</span>; len &lt;= n; len+=<span class="number">2</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span> ; i+len-<span class="number">1</span> &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> j = i + len - <span class="number">1</span>; <span class="comment">//右边界</span></span><br><span class="line">            <span class="keyword">int</span> mid = i + (j-i)/<span class="number">2</span>; <span class="comment">//中点</span></span><br><span class="line">            <span class="comment">//0,3</span></span><br><span class="line">            <span class="keyword">long</span> hleft = getHash(hashSum, pow, s, i, mid);</span><br><span class="line">            <span class="keyword">long</span> hright = getHash(hashSum, pow, s, mid+<span class="number">1</span>, j);</span><br><span class="line">            <span class="keyword">if</span>(hleft == hright &amp;&amp; !set.contains(hleft))&#123;</span><br><span class="line">                set.add(hleft);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> set.size();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 求s[i,j]区间的哈希值: s[i]*B^j-i + s[i+1]*B^j-i-1 + ... + s[j]</span></span><br><span class="line"><span class="comment">// </span></span><br><span class="line"><span class="comment">// hashSum[i] = s[0]*B^i-1 + s[1]*B^i-2 +...+ s[i-1]</span></span><br><span class="line"><span class="comment">// hashSum[j+1] = s[0]*B^j + s[1]*B^j-1 +...+ s[j]</span></span><br><span class="line"><span class="comment">// hashSum[i]*B^j-i+1 = s[0]*B^j + s[1]*B^j-1 +...+ s[i-1]*B^j-i+1</span></span><br><span class="line"><span class="comment">// hash[i,j] = hashSum[j+1] - hashSum[i] * B^j-i+1</span></span><br><span class="line"><span class="comment">//           = s[i]*B^j-i + s[i+1]*B^j-i-1 +...+s[j]</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">long</span> <span class="title">getHash</span><span class="params">(<span class="keyword">long</span>[] hashSum, <span class="keyword">long</span>[] pow, String s, <span class="keyword">int</span> i, <span class="keyword">int</span> j)</span></span>&#123;</span><br><span class="line">    <span class="comment">//j-i+1是[i,j]区间的长度，包含i和j，而hashSum[k]是不包含k的</span></span><br><span class="line">    <span class="comment">//所以这里需要转换下，j需要+1使得hashSum包含j</span></span><br><span class="line">    <span class="keyword">return</span> (hashSum[j+<span class="number">1</span>] - (hashSum[i] * pow[j-i+<span class="number">1</span>]) % MOD + MOD) % MOD;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>KMP的做法肯定就是参考KMP的<a href="http://imlgw.top/2020/05/13/kmp-suan-fa/#459-%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2">459. 重复的子字符串</a>的做法，我看了外网的discuss，只看见了一个这样写的，而且看不太懂，我自己尝试了下，感觉好多地方都会有坑，主要就是去重很麻烦，代码如下</p>
<p>下面为错误解法，无法通过OJ，懒得改了，感觉不是个很好的做法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//KMP的做法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">distinctEchoSubstrings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.length(); i++) &#123;</span><br><span class="line">        getNext(s.substring(i));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> set.size();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">HashSet&lt;String&gt; set = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">getNext</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s.length() &lt; <span class="number">2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n = s.length();</span><br><span class="line">    <span class="keyword">int</span>[] next = <span class="keyword">new</span> <span class="keyword">int</span>[n+<span class="number">1</span>];</span><br><span class="line">    next[<span class="number">0</span>] = -<span class="number">1</span>;</span><br><span class="line">    next[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">while</span>(right &lt;= n)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(left) == s.charAt(right-<span class="number">1</span>))&#123;</span><br><span class="line">            left++;</span><br><span class="line">            next[right] = left;</span><br><span class="line">            <span class="keyword">int</span> replen = right-next[right];</span><br><span class="line">            String rs = s.substring(<span class="number">0</span>,replen);</span><br><span class="line">            <span class="keyword">if</span> (right%<span class="number">2</span>==<span class="number">0</span> &amp;&amp; replen!=right &amp;&amp; right%replen==<span class="number">0</span> &amp;&amp; !set.contains(rs)) &#123;</span><br><span class="line">                set.add(rs);</span><br><span class="line">            &#125;</span><br><span class="line">            right++;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[left] == -<span class="number">1</span>)&#123;</span><br><span class="line">            right++;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left = next[left];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：Rabin-Karp算法</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-07-01 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/07/01/194514a9/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/07/03/a9fb61a5/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LeetCode位运算</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/06/20/96e38ff1/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Linux磁盘与文件系统</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/07/01/194514a9/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1044-%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E4%B8%B2"><span class="nav-number">1.</span> <span class="nav-text">1044. 最长重复子串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#718-%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84"><span class="nav-number">2.</span> <span class="nav-text">718. 最长重复子数组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%98-17-13-%E6%81%A2%E5%A4%8D%E7%A9%BA%E6%A0%BC"><span class="nav-number">3.</span> <span class="nav-text">面试题 17.13. 恢复空格</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1316-%E4%B8%8D%E5%90%8C%E7%9A%84%E5%BE%AA%E7%8E%AF%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">4.</span> <span class="nav-text">1316. 不同的循环子字符串</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
